Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/subtrees-and-paths/problem?isFullScreen=true
In this HackerRank in Data Structures -
Given a rooted tree of N nodes, where each node is uniquely numbered in between [1..N]. The node 1 is the root of the tree. Each node has an integer value which is initially 0.
You need to perform the following two kinds of queries on the tree:
- add t value: Add value to all nodes in subtree rooted at t
- max a b: Report maximum value on the path from a to b
Input Format
First line contains N, number of nodes in the tree. Next N-1 lines contain two space separated integers x and y which denote that there is an edge between node x and node y.
Next line contains Q, the number of queries to process.
Next Q lines follow with either add or max query per line.
Constraints
1 <= N <= 10**5
1 <= Q <= 10**5
1 <= t,a,b,x,y <= N
x not= y
-10**4 <= value <= 10**4
Output Format
For each max query output the answer in a separate line.
Sample Input
5
1 2
2 3
2 4
5 1
6
add 4 30
add 5 20
max 4 5
add 2 -20
max 4 5
max 3 4
Sample Output
30
20
10
Explanation
In the test case we have the following tree:
Initially all node values are zero.
Queries are performed in the following way:
add 4 30 // add 30 to node 4
add 5 20 // add 20 to node 5
max 4 5 // maximum of nodes 4,2,1,5 is 30
add 2 -20 // subtract 20 from nodes 2,3,4
max 4 5 // maximum of nodes 4,2,1,5 is 20
max 3 4 // maximum of nodes 3,2,4 is 10
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1000000007
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
int max;
int off;
} tree;
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void dfs2(int u);
void preprocess();
int lca(int a,int b);
int sum(int v,int tl,int tr,int l,int r,tree *t);
int min(int x,int y);
int max(int x,int y);
int solve(int x,int ancestor);
void range_update (int v, int tl, int tr, int pos1, int pos2, int new_val,tree *t);
void push(int v,int tl,int tr,tree *t);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
char str[10];
int N,NN,cn,level[100000],DP[18][100000],subtree_size[100000],special[100000],node_chain[100000],node_idx[100000],chain_head[100000],chain_len[100000]={0};
int *range_upt,chain_order[100000],node_begin[100000],node_end[100000],con=0;
lnode *table[100000]={0};
tree *chain[100000];
int main(){
int Q,x,y,i;
scanf("%d",&N);
for(i=0;i < N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
preprocess();
scanf("%d",&Q);
while(Q--){
scanf("%s",str);
switch(str[0]){
case 'a':
scanf("%d%d",&x,&y);
range_increment(node_begin[x-1],node_end[x-1],y);
if(node_idx[x-1])
range_update(1,0,chain_len[node_chain[x-1]]-1,node_idx[x-1],chain_len[node_chain[x-1]]-1,y,chain[node_chain[x-1]]);
break;
default:
scanf("%d%d",&x,&y);
i=lca(x-1,y-1);
printf("%d\n",max(solve(x-1,i),solve(y-1,i)));
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 || subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
chain_head[cn]=x->x;
dfs1(x->x,cn++);
}
return;
}
void dfs2(int u){
lnode *x;
node_begin[u]=con;
if(!node_idx[u])
chain_order[node_chain[u]]=con++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
dfs2(x->x);
node_end[u]=con-1;
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<18;i++)
for(j=0;j < N;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
chain_head[0]=0;
dfs1(0,0);
for(i=0;i < cn;i++){
chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree));
memset(chain[i],0,4*chain_len[i]*sizeof(tree));
}
range_upt=malloc(4*cn*sizeof(int));
init(cn);
dfs2(0);
return;
}
int lca(int a,int b>{
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<18;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b>return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
int sum(int v,int tl,int tr,int l,int r,tree *t){
push(v,tl,tr,t);
if(l>r)
return -INF;
if(l==tl && r==tr)
return t[v].max;
int tm=(tl+tr)/2;
return max(sum(v*2,tl,tm,l,min(r,tm),t),sum(v*2+1,tm+1,tr,max(l,tm+1),r,t));
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y>{
return (x>y)?x:y;
}
int solve(int x,int ancestor){
int ans=-INF;
while(node_chain[x]!=node_chain[ancestor]){
ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],chain[node_chain[x]])+query(chain_order[node_chain[x]]));
x=DP[0][chain_head[node_chain[x]]];
}
ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,node_idx[ancestor],node_idx[x],chain[node_chain[x]])+query(chain_order[node_chain[x]]));
return ans;
}
void range_update (int v, int tl, int tr, int pos1, int pos2, int new_val,tree *t) {
push(v,tl,tr,t);
if(pos2 < tl || pos1>tr)
return;
if (pos1<=tl && pos2>=tr)
t[v].off += new_val;
else {
int tm = (tl + tr) / 2;
range_update (v*2, tl, tm, pos1,pos2, new_val,t);
range_update (v*2+1, tm+1, tr, pos1,pos2, new_val,t);
push(v*2,tl,tm,t);
push(v*2+1,tm+1,tr,t);
t[v].max = max(t[v*2].max , t[v*2+1].max);
}
}
void push(int v,int tl,int tr,tree *t){
if(!t[v].off)
return;
t[v].max+=t[v].off;
if(tl!=tr){
t[2*v].off+=t[v].off;
t[2*v+1].off+=t[v].off;
}
t[v].off=0;
return;
}
void init( int n ){
NN = 1;
while( NN < n ) NN *= 2;
int i;
for( i = 1; i < NN + n; i++ ) range_upt[i] = 0;
}
void range_increment( int i, int j, int val ){
for( i += NN, j += NN; i < = j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) range_upt[i] += val;
if( j % 2 == 0 ) range_upt[j] += val;
}
}
int query( int i ){
int ans = 0,j;
for( j = i + NN; j; j /= 2 > ans += range_upt[j];
return ans;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
#define repu(i, a, b) for (int i = (a); i < (b); ++i)
#define repd(i, a, b) for (int i = (a); i > (b); --i)
#define mem(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define uni(a) a.erase(unique(all(a)), a.end())
#define count_bits(x) __builtin_popcount(x)
#define count_bitsll(x) __builtin_popcountll(x)
#define least_bits(x) __builtin_ffs(x)
#define least_bitsll(x) __builtin_ffsll(x)
#define most_bits(x) 32 - __builtin_clz(x)
#define most_bitsll(x) 64 - __builtin_clz(x)
vector < string> split(const string &s, char c) {
vector<string> v;
stringstream ss(s);
string x;
while (getline(ss, x, c)) v.push_back(x);
return v;
}
#define error(args...) { vector < string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector < string>::iterator it) {}
template
void err(vector<string>::iterator it, T a, Args... args) {
cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
err(++it, args...);
}
typedef long long ll;
const int MOD = 1000000007;
template < class T> inline T tmin(T a, T b) {return (a < b) ? a : b;}
template inline T tmax(T a, T b) {return (a > b) ? a : b;}
template < class T> inline void amax(T &a, T b) {if (b > a) a = b;}
template inline void amin(T &a, T b) {if (b < a) a = b;}
template < class T> inline T tabs(T a) {return (a > 0) ? a : -a;}
template T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;}
#define MAX_LOG 19
#define MAXN 100005
int n;
vector<int> G[MAXN];
/* HLD */
int chain_head[MAXN], pos_base[MAXN], chain_index[MAXN], end_sub[MAXN];
int ptr, num_chain;
/* LCA */
int par[MAX_LOG][MAXN], depth[MAXN], subtree[MAXN];
/* ST */
struct node {
int maxi, lazy;
} st[MAXN * 4];
/* LCA */
void dfs(int v, int p, int d) {
par[0][v] = p;
depth[v] = d;
subtree[v] = 1;
repu(i, 0, G[v].size()) {
if (G[v][i] != p) {
dfs(G[v][i], v, d + 1);
subtree[v] += subtree[G[v][i]];
}
}
}
void init() {
dfs(1, -1, 0);
for (int k = 0; k + 1 < MAX_LOG; ++k) {
for (int v = 1; v < = n; ++v) {
if (par[k][v] < 0) par[k + 1][v] = -1;
else par[k + 1][v] = par[k][par[k][v]];
}
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < MAX_LOG; ++k) {
if ((depth[u] - depth[v]) >> k & 1) {
v = par[k][v];
}
}
if (u == v) return u;
for (int k = MAX_LOG - 1; k >= 0; --k) {
if (par[k][u] != par[k][v]) {
u = par[k][u];
v = par[k][v];
}
}
return par[0][u];
}
/* Segment tree */
inline void lazy_eval(int ind, int len) {
if (st[ind].lazy != 0) {
st[ind].maxi += st[ind].lazy;
if (len > 1) {
int c1 = ind << 1, c2 = c1 | 1;
st[c1].lazy += st[ind].lazy;
st[c2].lazy += st[ind].lazy;
}
st[ind].lazy = 0;
}
}
void build_tree(int ind, int s, int e) {
if(s == e - 1) {
st[ind].maxi = st[ind].lazy = 0;
return;
}
int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1;
build_tree(c1, s, m);
build_tree(c2, m, e);
st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi);
st[ind].lazy = 0;
}
void update_tree(int ind, int s, int e, int ss, int ee, int val) {
lazy_eval(ind, e - s);
if (s >= ee || e <= ss> return;
if (s >= ss && e < = ee) {
st[ind].lazy += val;
lazy_eval(ind, e - s);
return;
}
int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1;
update_tree(c1, s, m, ss, ee, val);
update_tree(c2, m, e, ss, ee, val);
st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi);
}
int query_tree(int ind, int s, int e, int ss, int ee) {
lazy_eval(ind, e - s);
if (s >= ee || e < = ss) return INT_MIN;
if (s >= ss && e <= ee) return st[ind].maxi;
int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1;
int vl = query_tree(c1, s, m, ss, ee);
int vr = query_tree(c2, m, e, ss, ee);
st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi);
return tmax(vl, vr);
}
/* Heavy light decomposition */
void build_hld(int u) {
if(chain_head[num_chain] == -1) chain_head[num_chain] = u;
chain_index[u] = num_chain;
pos_base[u] = ptr++;
int most = 0, dem = -1;
repu(i, 0, G[u].size()) {
int v = G[u][i];
if (v != par[0][u]) {
if (subtree[v] > most) {
most = subtree[v];
dem = v;
}
}
}
if (dem != -1) build_hld(dem);
repu(i, 0, G[u].size()) {
int v = G[u][i];
if (v != par[0][u] && v != dem) {
++num_chain;
build_hld(v);
}
}
end_sub[u] = ptr;
}
/* query on path u -> v */
int query_hld(int u, int v) {
int ans = INT_MIN;
int uchain, vchain = chain_index[v];
/* interval [x, y) */
while (1) {
uchain = chain_index[u];
if (uchain != vchain) {
int tmp = query_tree(1, 0, ptr, pos_base[chain_head[uchain]], pos_base[u] + 1);
/* process something here */
amax(ans, tmp);
u = chain_head[uchain];
u = par[0][u];
}
else {
int tmp = query_tree(1, 0, ptr, pos_base[v], pos_base[u] + 1);
/* process something here */
amax(ans, tmp);
break;
}
}
return ans;
}
/* update value on path u -> v */
void update_hld(int v, int val) {
int s = pos_base[v], e = end_sub[v];
update_tree(1, 0, ptr, s, e, val);
}
int main(int argc, char *argv[]) {
ios_base::sync_with_stdio(false);
int q, a, b;
string op;
mem(chain_head, -1);
ptr = num_chain = 0;
cin >> n;
repu(i, 1, n) {
cin >> a >> b;
G[a].push_back(b); G[b].push_back(a);
}
init();
build_hld(1);
build_tree(1, 0, n);
cin >> q;
repu(i, 0, q) {
cin >> op >> a >> b;
if (op[0] == 'a') update_hld(a, b);
else {
int p = lca(a, b);
int res = query_hld(a, p);
amax(res, query_hld(b, p));
printf("%d\n", res);
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
static class Node {
int to;
int next;
}
static int cnt = 0;
static int[] head;
static Node[] e;
static void insert(int u, int v) {
e[++cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
static int[][] fa;
static int[] deep;
static int[] size;
static boolean[] vis;
static class NodeDfs1 {
int x;
int p;
boolean start = true;
public NodeDfs1(int x, int p) {
this.x = x;
this.p = p;
}
}
static void dfs1(int x) {
Deque < NodeDfs1> deque = new LinkedList<>();
deque.add(new NodeDfs1(x, -1));
while (!deque.isEmpty()) {
NodeDfs1 node = deque.pollLast();
size[node.x] = 1;
vis[node.x] = true;
for (int i = 1; i < = 20; i++) {
if (deep[node.x] < (1 << i)) break;
fa[node.x][i] = fa[fa[node.x][i - 1]][i - 1];
}
for (int i = head[node.x]; i > 0; i = e[i].next) {
if (vis[e[i].to]) continue;
deep[e[i].to] = deep[node.x] + 1;
fa[e[i].to][0] = node.x;
deque.add(new NodeDfs1(e[i].to, x));
}
if (node.p >= 0) {
size[node.p] += size[node.x];
}
}
}
static int sz = 0;
static int[] pos;
static int[] belong;
static int[] endpos;
static class NodeDfs2 {
int x;
int chain;
int k = 0;
int step = 0;
public NodeDfs2(int x, int chain) {
this.x = x;
this.chain = chain;
}
}
static void dfs2(int x, int chain) {
Deque < NodeDfs2> deque = new LinkedList<>();
deque.add(new NodeDfs2(x, chain));
while (!deque.isEmpty()) {
NodeDfs2 node = deque.peekLast();
if (node.step == 0) {
sz++;
pos[node.x] = sz;
belong[node.x] = node.chain;
for (int i = head[node.x]; i > 0; i = e[i].next) {
if (deep[e[i].to] > deep[node.x] && size[e[i].to] > size[node.k]) {
node.k = e[i].to;
}
}
if (node.k == 0) {
endpos[node.x] = sz;
deque.removeLast();
} else {
deque.add(new NodeDfs2(node.k, node.chain));
node.step = 1;
}
} else if (node.step == 1) {
for (int i = head[node.x]; i > 0; i = e[i].next) {
if (deep[e[i].to] > deep[node.x] && node.k != e[i].to) {
deque.add(new NodeDfs2(e[i].to, e[i].to));
}
}
node.step = 2;
} else if (node.step == 2) {
endpos[node.x] = sz;
deque.removeLast();
}
}
}
static int lca(int x, int y) {
if (deep[x] < deep[y]) {
int tmp = x;
x = y;
y = tmp;
}
int t = deep[x] - deep[y];
for (int i = 0; i < = 20; i++) {
if ( (t & (1 << i)) != 0) {
x = fa[x][i];
}
}
for (int i = 20; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i]; y = fa[y][i];
}
}
return (x == y) ? x : fa[x][0];
}
static int[] tree;
static int[] lazy;
static void update(int node, int a, int b, int i, int j, int value) {
if (lazy[node] != 0) {
tree[node] += lazy[node];
if (a != b) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
if (a > b || a > j || b < i) return;
if (a >= i && b <= j) {
tree[node] += value;
if (a != b) {
lazy[node * 2] += value;
lazy[node * 2 + 1] += value;
}
return;
}
update(node * 2, a, (a + b) / 2, i, j, value);
update(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);
tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
}
static int queryTree(int node, int a, int b, int i, int j) {
if (a > b || a > j || b < i) return Integer.MIN_VALUE;
if (lazy[node] != 0) {
tree[node] += lazy[node];
if (a != b)
{
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
if (a >= i && b < = j)
return tree[node];
int q1 = queryTree(node * 2, a, (a + b) / 2, i, j);
int q2 = queryTree(1 + node * 2, 1 + (a + b) / 2, b, i, j);
int res = Math.max(q1, q2);
return res;
}
static int solvemx(int n, int x, int f) {
int mx = Integer.MIN_VALUE;
while (belong[x] != belong[f]) {
mx = Math.max(mx, queryTree(1, 1, n, pos[belong[x]], pos[x]));
x = fa[belong[x]][0];
}
mx = Math.max(mx, queryTree(1, 1, n, pos[f], pos[x]));
return mx;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
e = new Node[(n+1)*2];
for (int i = 0; i < = n*2; i++) {
e[i] = new Node();
}
head = new int[n+1];
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
insert(u, v);
insert(v, u);
}
fa = new int[n+1][21];
deep = new int[n+1];
size = new int[n+1];
belong = new int[n+1];
endpos = new int[n+1];
vis = new boolean[n+1];
dfs1(1);
pos = new int[n+1];
dfs2(1, 1);
tree = new int[n * 4];
lazy = new int[n * 4];
st = new StringTokenizer(br.readLine());
int q = Integer.parseInt(st.nextToken());
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
if ("add".equals(str)) {
update(1, 1, n, pos[x], endpos[x], y);
} else {
int t = lca(x, y);
bw.write(Math.max(solvemx(n, x, t), solvemx(n, y, t)) + "\n");
}
}
bw.close();
br.close();
}
}